import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 15. 三数之和
 * <a href="https://leetcode.cn/problems/3sum/description/">...</a>
 * User: DELL
 * Date: 2023-09-12
 * Time: 23:03
 */
public class Solution {
    /**
     * 解题思路: (排序+双指针)
     * 首先对于本题来说,进行三重递归暴力求解肯定是不行的,因为那样子时间复杂度达到了O(n^3),
     * 这肯定是不行的,因此只能另寻他路.
     * 而对于本题来说,可以参照 两数之和 的思想,即先确定一个数即 nums[i],那么只需要在剩下的
     * 数组中找到满足 nums[j] + num[k] == -nums[i] 的所有 (j,k) 二元组即可.
     * 那么问题就转变为如何高效的在剩余的元素中找到满足以上关系的所有 (j,k) 二元组.
     * 我们可以在进行操作前先对 nums 数组进行排序,因为排序后我们一方面可以很轻松的处理
     * 重复元素的问题,同时也可以利用双指针法实现快速找寻满足以上关系的所有 (j,k) 二元组.
     * 即先定义左指针 left 和右指针 right,同时判断 nums[left] + num[right] 和 nums[i]的关系
     * 若 nums[left] + nums[right] < nums[i]: 则 left++
     * 若 nums[left] + nums[right] > nums[i]: 则 right--
     * 若 nums[left] + nums[right] == nums[i]: 则将当前元组放到结果列表中,
     * 同时因为满足要求的元组不止一个,因此这里需要继续进行下去,同时要注意在当前情况
     * 下, left++ 和 right-- 时要规避重复元素
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 对 nums 数组进行排序,方便去重
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 到达这里即把三数之和问题转换为了两数之和问题
            // 使用左右分别遍历的方法即可
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] < 0) {
                    left++;
                } else if (nums[left] + nums[right] + nums[i] > 0) {
                    right--;
                } else {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    res.add(temp);
                    // 调整 left 和 right 的值,同时注意跳过同样的值
                    while (++left < right && nums[left] != nums[left - 1]) ;
                    while (left < --right && nums[right] != nums[right + 1]) ;
                }
            }
        }
        return res;
    }
}